y.; "再帰的関数"
http://iso.2022.jp/math/undecidable-problems/files/recursive-function.pdf
著者
y.
メモ
Gödelのβ関数（とは呼んでおらずデコード関数と呼んでいる）が原始再帰的関数である簡単な証明がある
再帰的関数はTuringマシンで計算可能の証明など
以下のCor1.
Q1. 原始再帰的関数の到達可能性問題
原始再帰的関数$ f:\N\to\Nと自然数$ k \in \Nについて，$ f(x) = kとなる$ xは存在するか？
Q2. 原始再帰的関数の等価性問題
原始再帰的関数$ f,g:\N\to\Nについて，任意の$ x \in \Nで$ f(x) = g(x)か？
Cor 1.
原始再帰的関数の到達可能性問題と原始再帰的関数の等価性問題は決定不能である．